Introduction
1. Why Study Distributed Systems?#
Most applications we use today are distributed, an estimated 90% of the software we interact with, including embedded software (a car’s control software runs across multiple cooperating electronic control units, ECUs). With ~8 billion mobile users and ~18 billion devices, distribution is everywhere. Even systems that appear centralized are internally distributed: a single Google search is answered not by one machine but by the cooperation of thousands, which together assemble the result page.
The goal of the course is not to study specific applications, but to treat distribution as a paradigm for designing systems, and to understand why building them correctly requires techniques beyond centralized programming.
2. The State of the Internet#
Distribution is already the rule rather than the exception, and the clearest way to see that is to look at the scale of the internet itself.
A snapshot of the internet’s scale (Censys report, early 2023):
- Over 740 million hosts, running roughly 1.3 billion HTTP services.
- ~18% hosted by a major cloud provider (Amazon, Oracle, Google, Azure).
- ~85% run on named hosts (in DNS); ~14-15% on unnamed hosts, reachable only via a known IP.
The internet is thus a strongly distributed, largely unregulated platform with many players, yet a few top players dominate. The single most-visited site is Google (8.5B+ searches/day, 100B+ visits/month); the second is YouTube, owned by the same company. Together, Google and YouTube generate more traffic than the next 50 websites combined.
3. Case Study: Google#
Among the many players on that platform a handful dominate, Google most of all. Because its architecture became a template the rest of the industry followed, it is the natural place to start.
Google’s design pioneered a key decision. As Eric Schmidt put it (2007), “Google is technologically a large supercomputer… a distributed supercomputer among many data centers.” The original goal was to build a giant processing machine, then build services (search, YouTube, Docs) on top of it.
The Key Decision: Reliability in Software, Not Hardware#
Google’s insight: there is no way to build custom hardware reliable enough at the scale they needed. So instead of expensive special hardware, they built a distributed system from commodity hardware and pushed all reliability into software (much as Microsoft became the first software-only company in the 1970s).
“It’s better to have twice as much hardware that’s not as reliable than half as much that’s more reliable… You have to provide reliability on a software level. If you’re running 10,000 machines, something is going to die every day.”, Jeff Dean, 2008
At that scale something fails every day, so you must tolerate crashes in software regardless, making cheap hardware the rational choice. (Google does invest heavily in networking and cooling, but not in hardware-level reliability.)
Scale and Facts#
- ~2,000,000 servers across ~36 data centers (up from ~450,000 in 2006).
- Uptime of “four nines” (99.99%); a single search touches 700-1,000 machines: some run by other companies, such as the services that pick the ads shown next to the results: a huge distributed application that lives for a few milliseconds.
- The Jupiter network fabric delivers >1 Petabit/sec of bisection bandwidth (however you cut the data center in half, that much bandwidth crosses the cut).
- ~$91-93B capex on real estate, equipment, and construction in 2025 (projected to roughly double, to $175-185B, in 2026).
- Search: ~100,000 queries/sec, 63% from mobile, ~15% never seen before (uncacheable). YouTube: >1B hours watched/day, ~720,000 hours uploaded/day (500 hrs/min).
Data center site selection prioritizes: cheap/green electricity; proximity to water (cooling); large land areas (space, privacy, security); skilled workforce; short network distance to other centers (the speed of light is the limiting factor); and tax incentives.
4. Beyond the Internet: Other Distributed Systems#
The internet and the services built on top of it are the most visible distributed systems, but not the only ones: others include intranets (banking, corporate systems, grids, clouds), home networks, personal area networks (PANs, phone + earphones + PC over Bluetooth), wireless sensor networks, the Internet of Things (IoT), and mobile networks. These platforms expose difficulties the internet usually hides.
Smaller ≠ Simpler: The Reliability Difference#
These are smaller than any cloud, but the key difference is platform reliability:
- The internet, though huge, is in practice stable and reliable (lost packets are usually re-delivered in milliseconds).
- A personal network is far less reliable: moving a phone ten meters or a dying battery breaks the link.
- IoT combines the worst of both: potentially huge scale and fundamental unreliability (tiny battery-powered devices that switch off ~90% of the time), yet an application may need to coordinate thousands of sensors.
Mobility#
- Nomadic: operate in different locations, but tolerate downtime during movement (switch off, move, restart).
- Base-station: connected to one base station at a time; the system migrates the connection between stations as transparently as possible (cellular networks).
- Ad hoc (typical of IoT): a device too far from a base station routes through another nearby device. No specialized routers, every node may forward data; topology is built from connectivity.
This complexity is often hidden by lower software layers (a mobile-app programmer ignores handover), but not always, sometimes you must implement that layer, or you are in an ad hoc network with no such layer.
5. Why Distribute?#
Having seen where distributed systems show up, the natural question is why we choose to build them at all. Several forces push in that direction.
- Economics: originally mainframes consolidated all processing; today the price/performance ratio favors distribution, you cannot build Google on one PC.
- Incremental growth and load balancing: easier to evolve and use resources uniformly.
- Inherent distribution: some apps are distributed by definition (banking, reservations, games, computer-supported cooperative work, messaging).
- Reliability: replicate work so a crash doesn’t bring down the whole system.
The catch: building a reliable distributed system is much harder than a reliable centralized one.
6. What’s Special? The Eight Fallacies of Distributed Computing#
That catch is what makes distributed systems special, and it justifies a dedicated course: distribution hides pitfalls captured by the eight fallacies (Peter Deutsch et al.), assumptions programmers unknowingly make, each leading to broken designs.
1. The Network Is Reliable#
The network, and even TCP, is not reliable. TCP solves exactly one failure: packet loss from congestion (it also re-orders segments delivered out of order, but in terms of loss congestion is the only case it handles). It uses acknowledgements and exponential backoff (wait 1, 2, 4, 8… slices), which assumes loss means congestion, so resending aggressively would worsen it. This is detrimental when loss is not congestion (e.g., two computers drifting out of Wi-Fi range, TCP backs off when it should retry faster).
Failure detection is also limited. Killing an application or unplugging a cable at either end gives an immediate exception, the local OS detects it and closes the sockets (or the network card raises a trap). But cutting a cable in the middle of the path (a network partition) is undetectable locally: TCP assumes a huge congestion that will eventually clear, so it waits and retries for hours before throwing an exception. If you test failure detection by hitting Ctrl-C, you are testing the wrong case.
2. Latency Is Zero#
Latency is non-zero, which breaks ordering. Broadcast a question; one peer broadcasts a reply. A third party can hear the reply before the question if links have different latencies, a message and its causal consequence arrive in anti-causal order.
3. Bandwidth Is Infinite#
Related to latency: bandwidth is finite, so a large message takes time, and differing link bandwidths create variable effective latency, again enabling out-of-order delivery.
4. The Network Is Secure#
Assuming the network is secure is wrong. Security is too large to cover here (it would need several courses), but it remains fundamental.
5. Topology Doesn’t Change#
Even if you measure latencies at startup, the application is still incorrect because topology changes: latencies vary over time, and a direct link can become indirect as the internet reconfigures.
6. There Is One Administrator#
Because no single administrator controls the whole system, the network is inevitably heterogeneous, and that changes how protocols behave in practice. A striking example comes from 9/11: Politecnico di Milano lost its direct route to US sites, yet those sites were still reachable through Vodafone’s mobile network. In principle BGP (Border Gateway Protocol) should have noticed the broken path and rerouted automatically. It did not, and the reason was administrative and economic rather than technical: Vodafone had no commercial agreement with Politecnico’s network provider, so it would not carry the traffic. The protocols needed to reroute existed; the commercial relationships that would have allowed it did not.
The episode has a bitter architectural footnote. IP was designed in the 1970s precisely to survive a global war, yet it could not survive two airplanes: the transatlantic link serving the Italian academic network landed in the basement of one of the two towers, and its backup cable, laid for redundancy, landed in the second tower, twenty meters away. When both fell, much of the European academic network lost its US connectivity at once. The protocols were sound; the people placing cables (and signing contracts) were the weak point.
7. Transport Cost Is Zero#
There is a real cost behind connections (and behind it, administrators and commercial agreements). Assuming free transport ignores the economic layer that actually governs routing.
8. The Network Is Homogeneous#
The network is heterogeneous in space (links differ in latency/bandwidth, the cause of out-of-order causal delivery) and in time (a link’s latency/bandwidth changes).
Bottom line: building correct distributed systems is much harder than centralized ones, and the extra complexity comes entirely from the network in the middle.
7. What Is a Distributed System? Three Definitions#
If the network in the middle is the real source of difficulty, the term itself deserves a precise meaning. Three classic definitions, each stressing a different facet, are worth keeping in mind.
Tanenbaum & van Steen: “A collection of independent computers that appears to its users as a single coherent system.”, independent means, fundamentally, no shared clock.
Coulouris, Dollimore & Kindberg: “Hardware or software components at networked computers that communicate and coordinate their actions only by passing messages.”, more precise: a network offers only message passing, and coordination implies synchronization/consensus.
Lamport: “One on which I cannot get any work done because some machine I’ve never heard of has crashed.”, captures what fault tolerance must defend against.
8. Parallel vs. Distributed Computing#
The definitions turn on two ideas, independence, and coordination by messages alone, and those same ideas separate a distributed system from a merely parallel one, a distinction that is easy to blur.
| Parallel system | Distributed system | |
|---|---|---|
| Processors | Multiple cores / CPUs | Multiple independent machines |
| Clock | A single shared clock | Many clocks, not synchronized |
| Memory | Shared memory | Each node has its own memory |
| Communication | Via shared memory | Only message passing (in hardware) |
Shared memory can be simulated in a distributed system, but only through complex protocols, because the hardware offers message passing alone.
9. Where Middleware Fits#
Because the hardware ultimately offers only message passing, the practical question is how much of that complexity an application has to face by itself. This is where middleware comes in.
Middleware is software that “sits in the middle,” underlying most distributed systems. Two ways to build a distributed application:
- Network/OS-based: the application sits directly on basic OS networking services (TCP/IP, RPC) and must solve all distribution problems itself.
- Middleware-based: a middleware layer offers higher-level services that hide as much distribution as possible, making the system look closer to a single machine.
This maps onto the two courses: DS (this course) builds directly on basic OS services, exposing the complexity (project: TCP sockets only, no middleware); Networked Software for Distributed Systems (NSDS) teaches the middleware technologies that implement, ready-made, much of what DS builds from scratch. Understanding the internals reveals those technologies’ limitations.
Middleware provides horizontal services (general, non-application-specific) and masks platform differences.
10. Defining Features of Distributed Systems#
Whether or not middleware hides them, a few features fundamentally set distributed systems apart from centralized ones.
| Feature | Centralized | Distributed |
|---|---|---|
| Concurrency | A design choice | A fact of life: multiple machines, multiple threads of control |
| Global clock | The physical clock aids synchronization | Clocks are many and unsynchronized |
| Failures | Typically total | Partial: components fail independently, others keep running |
Why no global clock matters (~99% of the complexity): a mutex can only be implemented with hardware help that relies on all cores sharing one clock, which makes atomic decisions (“did I acquire the lock?”) possible. Without a single clock, this must be simulated via complex protocols, the heart of the course.
Why partial failure matters: if LibreOffice crashes because your CPU fails, you can’t blame the programmer (total failure). But if Microsoft 365 loses your work because 1 of 10,000 machines crashed, you would, distributed failures are partial and must be tolerated. Recovery is harder because the application state is itself distributed.
11. Challenges in Building Distributed Systems#
These defining features translate into a recurring set of challenges that every distributed system has to confront.
Heterogeneity, of hosts, networks (differences at OSI layers 1-2 matter even under TCP/IP), hardware (data representation), operating systems (networking APIs, Java thread semantics), and languages (different data representations; distributed systems commonly mix languages).
Openness, determines whether a system can be extended and re-implemented. Requires publishing key aspects (protocols, interfaces), adopting standards, and easing interoperability/portability. Internet case: RFCs and the IETF.
Security, the CIA triad: Confidentiality (no unauthorized disclosure), Integrity (no alteration/corruption), Availability (no interference with access, DoS). Encryption helps but leaves open issues (DoS, mobile code, content-based routing).
Scalability, growth (users, geographic/administrative span) with the lowest performance impact: performance should degrade roughly linearly with load (1s→1min is scalable; 1s→15yrs is not). Avoid centralized services/data/algorithms; use decentralized algorithms (local information only, no global clock, one machine’s failure doesn’t ruin the algorithm). Techniques: async communication, caching/replication, epidemic dissemination, hierarchical structuring.
Failure handling, Detecting (some easy via checksums; a remote crash is impossible to confirm, you can’t tell whether the request, the server, or just the acknowledgement was lost; an agreement problem, generally unsolvable, so failures can only be suspected); Masking (e.g., retransmit); Tolerating (shift work to others, degrade gracefully); Recovering (checkpoint state, but from which point do you restart, given others advanced?); Redundancy (replicate, but keeping replicas in sync is hard).
Concurrency, a fact, not a choice; shared resources must be synchronized without a physical clock or shared memory (no cross-machine synchronized or mutex).
Transparency, hide as much as possible to simplify life for programmers and users.
12. Transparency#
The last of those challenges, transparency, matters enough to deserve its own breakdown. The aim is to hide each form of distribution behind one coherent interface.
| Transparency | What it hides |
|---|---|
| Access | Differences in data representation / how a resource is accessed |
| Location | Where a resource is located |
| Migration | That a resource may move to another location |
| Relocation | That a resource may move while in use |
| Replication | That a resource may be replicated |
| Concurrency | That a resource is shared by competing users |
| Failure | The failure and recovery of a resource |
| Persistence | Whether a resource is in memory or on disk |
Location transparency enables migration: location-independent access lets a component move from a crashed to a running machine while clients keep using the same logical component. Limits: some things can’t be hidden (time zones, delays), and hiding too much hurts performance (e.g., repeatedly accessing a remote object as if local).
13. Course Outline#
The rest of the course develops these ideas in roughly the order they build on one another.
- Modeling distributed systems
- Communication models (protocols on top of TCP)
- Naming: addressing the peer you communicate with
- Synchronization: hard because each machine has its own clock
- Fault tolerance
- Consensus: the agreement problem behind failure detection; generally unsolvable
- Consistency and Replication
- Big data
- Peer-to-peer computing
- Simulation with OMNeT++, not on the written test, but useful for a simulated project
A note on the exam: no past written-exam question targets this introductory chapter directly; the exam material starts with the topics of the next chapters, each of which closes with its own worked “Exam questions” section.